package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
public class NC126 {
    public class Solution {
        public int minMoney1 (int[] arr, int aim) {
            if (arr == null || arr.length == 0) return 0;
            return dfs(arr, aim, 0);
        }

        public int dfs(int[] arr, int cur, int idx) {
            if (idx == arr.length) {
                return cur == 0 ? 0 : -1;
            } 

            int t, res = Integer.MAX_VALUE, temp;
            for (int i = 0; (t = cur - i * arr[idx]) >= 0; i++) {
                temp = dfs(arr, t, idx + 1);
                if (temp < 0) continue;
                res = Math.min(res, temp + i);
            }
            if (res == Integer.MAX_VALUE) return -1;
            return res;
        }

        public int minMoney (int[] arr, int aim) {
            if (arr == null || arr.length == 0) return 0;
            int len = arr.length;
            int[][] f = new int[len + 1][aim + 1];

            //完成目标才是可行解
            for (int i = 1; i <= aim; i++) {
                f[len][i] = Integer.MAX_VALUE;
            }
            f[len][0] = 0;

            int t;
            for (int i = len - 1; i >= 0; i--) {
                for(int j = 0; j <= aim; j++) {
                    f[i][j] = f[i + 1][j];
                    if (j >= arr[i] && f[i][j - arr[i]] != Integer.MAX_VALUE)
                         f[i][j] = Math.min(f[i][j], f[i][j - arr[i]] + 1);
                    /* for (int k = 1; (t = k * arr[i]) <= j; k++) {
                        if (f[i + 1][j - t] == Integer.MAX_VALUE) continue;
                        f[i][j] = Math.min(f[i][j], f[i + 1][j - t] + k);
                    } */
                }
            }

            return f[0][aim] == Integer.MAX_VALUE ? -1 : f[0][aim];
        }
    }

    @Test
    public void test() {
        /* 
        [2887,2355,335,4472,4561,1819,3808],4953
        */
        Solution s = new Solution();
        int[] nums = new int[]{2887,2355,335,4472,4561,1819,3808};
        // nums = new int[]{2,3,5};
        int res = s.minMoney(nums, 4953);
        System.out.println(res);
    }
}
